class Solution {
	bool **map;
	int m, n;
	bool exi(vector<vector<char>>& board, string word, bool **map, int x, int y) {
		if (board[x][y] == word[0]) {
			if (word.length() <= 1) return true;
			map[x][y] = true;
			if (x + 1 < m && map[x + 1][y] == false) {
				if (exi(board, word.substr(1, word.length() - 1), map, x + 1, y)) return true;
			}
			if (x > 0 && map[x - 1][y] == false) {
				if (exi(board, word.substr(1, word.length() - 1), map, x - 1, y)) return true;
			}
			if (y + 1 < n && map[x][y + 1] == false) {
				if (exi(board, word.substr(1, word.length() - 1), map, x, y + 1)) return true;
			}
			if (y > 0 && map[x][y - 1] == false) {
				if (exi(board, word.substr(1, word.length() - 1), map, x, y - 1)) return true;
			}
		}
		map[x][y] = false;
		return false;
	}
public:
	bool exist(vector<vector<char>>& board, string word) {
	    if (board.size() == 0 || board[0].size() == 0) return false;
		n = board[0].size(), m = board.size();
		map = (bool**)malloc(m * sizeof(bool*));
		for (int i = 0; i < m; ++i) {
			map[i] = (bool*)malloc(n * sizeof(bool));
			memset(map[i], false, n * sizeof(bool));
		}
		for (int i = 0; i < m; ++i)
		for (int j = 0; j < n; ++j) {
			if (exi(board, word, map, i, j)) {
			        for (int i = 0; i < m; ++i) free(map[i]);
		                free(map);
		                return true;
			}
		}
		for (int i = 0; i < m; ++i) free(map[i]);
		free(map);
		return false;
	}
};
